package com.LeeCode;

import java.util.Arrays;

/**
 * 运动员和训练师的最大匹配数
 */

public class Code2410 {
    public static void main(String[] args) {
        int[] players = {4, 7, 9};
        int[] trainers = {8, 2, 5, 8};
        System.out.println(new Code2410().matchPlayersAndTrainers1(players, trainers));
    }

    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        int n = players.length, m = trainers.length;
        Arrays.sort(players);
        Arrays.sort(trainers);
        int left = 0, right = Math.min(n, m) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (check(players, trainers, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(int[] players, int[] trainers, int k) {
        int start = trainers.length - k;
        for (int i = 0; i < k; i++) {
            if (players[i] > trainers[start + i])
                return false;
        }
        return true;
    }

    public int matchPlayersAndTrainers1(int[] players, int[] trainers) {
        int n = players.length, m = trainers.length;
        Arrays.sort(players);
        Arrays.sort(trainers);
        int index = 0;
        for (int i = 0; i < n; i++) {
            int player = players[i];
            while (index < m && player > trainers[index])
                index++;
            if (index == m)
                return i;
            index++;
        }
        return n;
    }
}
